{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Preimage Size of Factorial Zeroes Function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: preimageSizeFZF"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #阶乘函数后 K 个零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>&nbsp;<code>f(x)</code>&nbsp;是&nbsp;<code>x!</code>&nbsp;末尾是 0 的数量。回想一下&nbsp;<code>x! = 1 * 2 * 3 * ... * x</code>，且 <code>0! = 1</code>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，&nbsp;<code>f(3) = 0</code>&nbsp;，因为 <code>3! = 6</code> 的末尾没有 0 ；而 <code>f(11) = 2</code>&nbsp;，因为 <code>11!= 39916800</code> 末端有 2 个 0 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定&nbsp;<code>k</code>，找出返回能满足 <code>f(x) = k</code>&nbsp;的非负整数 <code>x</code>&nbsp;的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong><strong> </strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 0<strong>\n",
    "输出：</strong>5<strong>\n",
    "解释：</strong>0!, 1!, 2!, 3!, 和 4!&nbsp;均符合 k = 0 的条件。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 5\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>没有匹配到这样的 x!，符合 k = 5 的条件。</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> k = 3\n",
    "<strong>输出:</strong> 5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [preimage-size-of-factorial-zeroes-function](https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [preimage-size-of-factorial-zeroes-function](https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['0', '5', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def zeta(n: int) -> int:\n",
    "            res = 0\n",
    "            while n:\n",
    "                n //= 5\n",
    "                res += n\n",
    "            return res\n",
    "\n",
    "        return bisect_left(range(5*(k+1)), k+1, key=zeta) - bisect_left(range(5*(k)), k, key=zeta)\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        return self.search(k + 1) - self.search(k)\n",
    "    \n",
    "    def search(self, k):\n",
    "        lo, hi = 0, 5 * k + 1\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            num = self.count_zeros(mid)\n",
    "            if num == k:\n",
    "                hi = mid\n",
    "            elif num > k:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo\n",
    "    \n",
    "    def count_zeros(self, x):\n",
    "        num = 0\n",
    "        while x:\n",
    "            num += x // 5\n",
    "            x = x // 5\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        if k<=4:\n",
    "            return 5\n",
    "        \n",
    "        l=4*k\n",
    "        r=25*k//6+5\n",
    "        def check(x):\n",
    "            a=0\n",
    "            while x:\n",
    "                t=x//5\n",
    "                a+=t\n",
    "                x=t\n",
    "            return a\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            x=check(mid)\n",
    "            if x==k:\n",
    "                return 5\n",
    "            elif x<k:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        \n",
    "        def check(n):\n",
    "            res = 0\n",
    "            while n > 0:\n",
    "                n//=5\n",
    "                res += n\n",
    "            return res\n",
    "        def bi(k):\n",
    "            l, r = 0, 5*k\n",
    "            mid = 0\n",
    "            while l <= r:\n",
    "                mid = (l+r)//2\n",
    "                if check(mid)>=k:\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "        return bi(k+1) - bi(k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "    \n",
    "        # input x, output the count of zeroes at the end of x!\n",
    "        def countOfFactorialZeroes(x):\n",
    "            count = 0\n",
    "            factor = 5\n",
    "            while x >= factor:\n",
    "                count += x // factor\n",
    "                factor *= 5\n",
    "            return count\n",
    "        \n",
    "        def leftbound(target):\n",
    "            left, right = 0, 2 ** 32 -1\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if countOfFactorialZeroes(mid) >= target:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "        \n",
    "        def rightbound(target):\n",
    "            left, right = 0, 2 ** 32 - 1\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if countOfFactorialZeroes(mid) <= target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return right\n",
    "\n",
    "        return rightbound(k) - leftbound(k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ks = [1]\n",
    "while ks[-1] < 1000000000:\n",
    "    ks.append(ks[-1] * 5 + 1)\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        for kk in reversed(ks):\n",
    "            if kk > k:\n",
    "                continue\n",
    "            if k >= 5 * kk:\n",
    "                return 0\n",
    "            k %= kk\n",
    "        return 5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        print(self.celonepreimage(k+1))\n",
    "        return self.celonepreimage(k+1)-self.celonepreimage(k)\n",
    "        \n",
    "    def celonepreimage(self,x) -> int:\n",
    "        left = 0\n",
    "        right = 5*x\n",
    "        while(left<=right):\n",
    "            mid = (right-left)//2+left\n",
    "            if self.trailingZeroes(mid)>=x:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "    \n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n>0:\n",
    "            n = n//5\n",
    "            count+=n\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # 存在的5有多少个，零就有多少个，因为2的个数永远比5的个数多\n",
    "        # 统计多少个数的阶乘末尾为k个零，实际求的是存在多少个数包含k个因子5\n",
    "        # 0 <= k <= 1e9\n",
    "        # 需要找到多少个数中包括这么多的5\n",
    "        # 1！：0 2！：0 3！：0 4！：0 5！：1 6！：1 7！：1 8！：1 9！：1 10！：2\n",
    "        # 5 10 15 20 25（到25的时候一次性增加了两个）\n",
    "        # f(x) 是单调递增的，所以可以采用二分查找进行求解\n",
    "        # 存在上界和下界\n",
    "        def check(x):\n",
    "            # 计算该数的阶乘有多少个因子5\n",
    "            cnt = 0\n",
    "            i = 1\n",
    "            while x >= 5 ** i:\n",
    "                cnt += x // (5 ** i)\n",
    "                i += 1\n",
    "            return cnt\n",
    "        l, r = 0, 10 ** 18\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid) >= k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        print(l)\n",
    "        al = l\n",
    "        l, r = 0, 10 ** 18\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid) >= k + 1:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        print(l)\n",
    "        return l - al\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "\n",
    "        l , r = 4 * k , 5*(k+1)\n",
    "\n",
    "        def check(num):\n",
    "            ans = 0\n",
    "            base = 5\n",
    "            while num >= base:\n",
    "                ans += num // base\n",
    "                base *= 5\n",
    "            return ans\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            d = check(mid)\n",
    "            if d < k:\n",
    "                l = mid + 1\n",
    "            elif d == k:return 5\n",
    "            else:\n",
    "                r = mid\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        #2，5，n*10的数量，注意25，125,625中包含多个5.\n",
    "        #n！的末尾0的数量=1,2,3....n中因数5的个数\n",
    "        #假设f(n)=(5**n)!的末尾0的个数，则分解k=a1*f(1)+a2*f(2)+...+ax*f(x)\n",
    "        #要求0<=ai<=4\n",
    "        f = {0:0}\n",
    "        zero_num = 0\n",
    "        n = 0\n",
    "        while zero_num <= k:\n",
    "            n += 1\n",
    "            zero_num = 5 ** (n-1) + zero_num\n",
    "            f[n] = zero_num\n",
    "\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if k // f[i] > 4:\n",
    "                return 0\n",
    "            k = k % f[i]\n",
    "        return 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def get(n):\n",
    "            ans = 0\n",
    "            while n != 0:\n",
    "                n //= 5\n",
    "                ans += n\n",
    "            return ans\n",
    "        \n",
    "        sol = lambda k: bisect.bisect_left(range(k * 5), k, key=get)\n",
    "        return sol(k+1) - sol(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            while num > 0:\n",
    "                cnt += num // 5\n",
    "                num //= 5\n",
    "            return cnt\n",
    "\n",
    "        left = 0\n",
    "        right = 10**10\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid) >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        res = 0\n",
    "        for i in range(left, left + 6):\n",
    "            if check(i) == k:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        return self.find(k+1)-self.find(k)\n",
    "        \n",
    "    def trailingZeroes(self, x: int) -> int:\n",
    "        res = 0\n",
    "        while x != 0:\n",
    "            x //= 5\n",
    "            res += x\n",
    "        return res\n",
    "    \n",
    "    def find(self, k):\n",
    "        left = 0\n",
    "        right = 5*k\n",
    "        while left < right:\n",
    "            mid = (left+right)//2\n",
    "            if k <= self.trailingZeroes(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid +1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            while num > 0:\n",
    "                cnt += num // 5\n",
    "                num //= 5\n",
    "            return cnt\n",
    "\n",
    "        left = 0\n",
    "        right = 5*(k+1)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid) >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        res = 0\n",
    "        for i in range(left, left + 6):\n",
    "            if check(i) == k:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def ZeroCnt(n: int) -> int:\n",
    "            res = 0\n",
    "            while n > 0:\n",
    "                n //= 5\n",
    "                res += n\n",
    "            return res\n",
    "        \n",
    "        # def GetRes(x: int) -> int: # 用二分查找库函数\n",
    "            # return bisect_left(range(5 * x), x, key=ZeroCnt)\n",
    "        \n",
    "        def GetRes(x: int) -> int:\n",
    "            left, right = 0, 5 * x\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if ZeroCnt(mid) < x:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return right + 1\n",
    "\n",
    "        return GetRes(k + 1) - GetRes(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        return int(self.right_bound(k) - self.left_bound(k)+1)\n",
    "\n",
    "    def left_bound(self, target: int) -> int:\n",
    "        lo, hi = 4 * target, 5 * (target + 1)\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if self.trailingZeroes(mid) < target:\n",
    "                lo = mid + 1\n",
    "            elif self.trailingZeroes(mid) > target:\n",
    "                hi = mid\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo\n",
    "\n",
    "    def right_bound(self, target: int) -> int:\n",
    "        lo, hi = 4 * target, 5 * (target + 1)\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if self.trailingZeroes(mid) < target:\n",
    "                lo = mid + 1\n",
    "            elif self.trailingZeroes(mid) > target:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo - 1\n",
    "\n",
    "    def trailingZeroes(self, n):\n",
    "        res = 0\n",
    "        base = 5\n",
    "        while base<=n:\n",
    "            res+=n//base\n",
    "            base *= 5\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        return int(self.right_bound(k) - self.left_bound(k)+1)\n",
    "\n",
    "    def left_bound(self, target: int) -> int:\n",
    "        MAX = 2 ** 63 - 1\n",
    "        lo, hi = 0, MAX\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if self.trailingZeroes(mid) < target:\n",
    "                lo = mid + 1\n",
    "            elif self.trailingZeroes(mid) > target:\n",
    "                hi = mid\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo\n",
    "\n",
    "    def right_bound(self, target: int) -> int:\n",
    "        MAX = 2 ** 63 - 1\n",
    "        lo, hi = 0, MAX\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if self.trailingZeroes(mid) < target:\n",
    "                lo = mid + 1\n",
    "            elif self.trailingZeroes(mid) > target:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo - 1\n",
    "\n",
    "    def trailingZeroes(self, n):\n",
    "        res = 0\n",
    "        base = 5\n",
    "        while base<=n:\n",
    "            res+=n//base\n",
    "            base *= 5\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def f(x):\n",
    "            return x//5+f(x//5) if x>0 else 0\n",
    "        return -bisect.bisect_left(range(5*k),k,key=f)+bisect.bisect_left(range(5*(k+1)),k+1,key=f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # 5的个数就是0的个数\n",
    "        # 这题最后的结果为5或者0\n",
    "        # 最后可以用二分法\n",
    "\n",
    "        # check这一步相当精炼\n",
    "        def check(num):\n",
    "            count = 0\n",
    "            while num:\n",
    "                count += num // 5\n",
    "                num //= 5\n",
    "            return count\n",
    "        \n",
    "        low, high = 0, 10 ** 10\n",
    "        while low <= high:\n",
    "            mid = (low + high) >> 1\n",
    "            # 循环不变量：check(high+1) >= k\n",
    "            if check(mid) >= k:\n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        \n",
    "        if check(high+1) == k:\n",
    "            return 5\n",
    "        return 0\n",
    "\n",
    "\n",
    "        # ans = 0\n",
    "        # for num in range(high+1, high+6):\n",
    "        #     if check(num) == k:\n",
    "        #         ans += 1\n",
    "        # return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def zeta(n):\n",
    "            res = 0\n",
    "            while n:\n",
    "                n//=5\n",
    "                res+=n\n",
    "            return res\n",
    "\n",
    "        def nx(k):\n",
    "            return bisect_left(range(5*k),k,key = zeta)\n",
    "\n",
    "        return nx(k+1) -nx(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def num_0(n):\n",
    "            res = 0\n",
    "            while n:\n",
    "                res += n // 5\n",
    "                n //= 5\n",
    "            return res\n",
    "        \n",
    "        le, ri = 0, 5*(k+1)\n",
    "        while le <= ri:\n",
    "            mid = le + (ri - le) // 2\n",
    "            if num_0(mid) == k:\n",
    "                return 5\n",
    "            elif num_0(mid) > k:\n",
    "                ri = mid-1\n",
    "            else:\n",
    "                le = mid+1\n",
    "        return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        print(self.celonepreimage(k+1))\n",
    "        return self.celonepreimage(k+1)-self.celonepreimage(k)\n",
    "        \n",
    "    def celonepreimage(self,x) -> int:\n",
    "        left = 0\n",
    "        right = 5*x\n",
    "        while(left<=right):\n",
    "            mid = (right-left)//2+left\n",
    "            if self.trailingZeroes(mid)>=x:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "    \n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n>0:\n",
    "            n = n//5\n",
    "            count+=n\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def zeta(n: int) -> int:\n",
    "            res = 0\n",
    "            while n:\n",
    "                n //= 5\n",
    "                res += n\n",
    "            return res\n",
    "        def calc(k: int) -> int:\n",
    "            return bisect_left(range(5 * k), k, key=zeta)\n",
    "        return calc(k + 1) - calc(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def zeta(x):\n",
    "            count = 0\n",
    "            while x // 5 > 0:\n",
    "                count += x//5\n",
    "                x //= 5\n",
    "            return count\n",
    "        def binary_search(left, right, target):\n",
    "            while left <= right:\n",
    "                mid = (left + right)//2\n",
    "                if zeta(mid) == target:\n",
    "                    return mid\n",
    "                elif zeta(mid) < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return -1\n",
    "        n1 = binary_search(4*k, 5*k, k)\n",
    "        if n1 == -1:\n",
    "            return 0\n",
    "        else:\n",
    "            return 5                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # 5的个数就是0的个数\n",
    "        # 这题最后的结果为5或者0\n",
    "        # 最后可以用二分法\n",
    "\n",
    "        # check这一步相当精炼\n",
    "        def check(num):\n",
    "            count = 0\n",
    "            while num:\n",
    "                count += num // 5\n",
    "                num //= 5\n",
    "            return count\n",
    "        \n",
    "        low, high = 0, 10 ** 10\n",
    "        while low <= high:\n",
    "            mid = (low + high) >> 1\n",
    "            # 循环不变量：check(high+1) >= k\n",
    "            if check(mid) >= k:\n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        \n",
    "        if check(high+1) == k:\n",
    "            return 5\n",
    "        return 0\n",
    "\n",
    "\n",
    "        # ans = 0\n",
    "        # for num in range(high+1, high+6):\n",
    "        #     if check(num) == k:\n",
    "        #         ans += 1\n",
    "        # return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        l,r=0,5*k+5\n",
    "        def check(u):return u//5+(0 if u<5 else check(u//5))\n",
    "        while(l<r):\n",
    "            mid=(l+r)>>1\n",
    "            q=check(mid)\n",
    "            if(q==k):return 5\n",
    "            elif(q<k):l=mid+1\n",
    "            else:r=mid\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        \n",
    "        def cnt(num):\n",
    "            mul = 5\n",
    "            ans = 0\n",
    "            while mul <= num:\n",
    "                ans += num // mul \n",
    "                mul *= 5\n",
    "            return ans\n",
    "\n",
    "        # <= k 的最大值\n",
    "        def check(k):\n",
    "            if k == -1:\n",
    "                return -1\n",
    "\n",
    "            left = 0\n",
    "            right = int(1e10)\n",
    "\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "\n",
    "                if cnt(mid) > k:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid\n",
    "            \n",
    "            return left\n",
    "\n",
    "  \n",
    "        \n",
    "        \n",
    "        return check(k) - check(k - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        return self.search(k + 1) - self.search(k)\n",
    "    \n",
    "    def count_zeros(self, num):\n",
    "        res = 0\n",
    "        while num:\n",
    "            res += num // 5\n",
    "            num //= 5\n",
    "        return res\n",
    "    \n",
    "    def search(self, k):\n",
    "        lo, hi = 0, 5 * k + 1\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            zeros = self.count_zeros(mid)\n",
    "            if zeros == k:\n",
    "                hi = mid\n",
    "            elif zeros > k:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        co, i = 1/5, 2\n",
    "        while (k * 5 >= 5 ** i):\n",
    "            co += 1 / (5 ** i)\n",
    "            i += 1\n",
    "        \n",
    "        begin = math.ceil(k / (co*5)) * 5\n",
    "        result = 0\n",
    "        while result < k:\n",
    "            result = 0\n",
    "            i = 1\n",
    "            while (begin // (5 ** i) > 0):\n",
    "                result += begin // (5 ** i)\n",
    "                i += 1\n",
    "\n",
    "            begin += 5\n",
    "\n",
    "        return 0 if result > k else 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ks = [1]\n",
    "while ks[-1] < 1000000000:\n",
    "    ks.append(ks[-1] * 5 + 1)\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        for kk in reversed(ks):\n",
    "            if kk > k:\n",
    "                continue\n",
    "            if k >= 5 * kk:\n",
    "                return 0\n",
    "            k %= kk\n",
    "        return 5\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numZero(self, k: int) -> int:\n",
    "        if k==0:\n",
    "            return 0\n",
    "        t = 0 \n",
    "        tk = k\n",
    "        while tk%5 == 0:\n",
    "            t += 1\n",
    "            tk /= 5\n",
    "        return self.numZero(k-1)+t\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # 5e13恰大于10e9\n",
    "        pp = []\n",
    "        t = 0\n",
    "        pp.append(1)\n",
    "        if k == 0:\n",
    "            return 5\n",
    "        for i in range(1,14):\n",
    "            pp.append(pp[i-1]*5+1)\n",
    "            if pp[i] > k and pp[i-1] <= k:\n",
    "                t = i\n",
    "                break\n",
    "        #p = []\n",
    "        #return self.numZero(505)\n",
    "        for i in range(t,0,-1):\n",
    "            #p.append([pp[i] - k%pp[i],i])\n",
    "            if pp[i] - k%pp[i] <= i:\n",
    "                return 0\n",
    "            k = k % pp[i]\n",
    "        return 5\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # 左边界和右边界之差+1\n",
    "        return self.right_bound(k)-self.left_bound(k)+1\n",
    "    \n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n // 5 > 0:\n",
    "            res += n // 5\n",
    "            n = n // 5\n",
    "        return res\n",
    "\n",
    "    # 搜索trailingZeroes(n) == k的左侧边界 \n",
    "    def left_bound(self, target):\n",
    "        lo = 0\n",
    "        hi = pow(2,63)\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi-lo)//2\n",
    "            if self.trailingZeroes(mid) < target:\n",
    "                lo = mid + 1\n",
    "            elif self.trailingZeroes(mid) > target:\n",
    "                hi = mid \n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo\n",
    "    \n",
    "    # 搜索trailingZeroes(n) == k的右侧边界 \n",
    "    def right_bound(self, target):\n",
    "        lo = 0\n",
    "        hi = pow(2,63)\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi-lo)//2\n",
    "            if self.trailingZeroes(mid) < target:\n",
    "                lo = mid + 1\n",
    "            elif self.trailingZeroes(mid) > target:\n",
    "                hi = mid \n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "\n",
    "        def zeta(n:int)->int:\n",
    "            cnt = 0\n",
    "            while n:\n",
    "                n //=5\n",
    "                cnt += n\n",
    "            return cnt\n",
    "        def nx(n:int)->int:\n",
    "            left,right =4*n,5*n\n",
    "            while left<right:\n",
    "                mid = (left+right)//2\n",
    "                if zeta(mid)<n:\n",
    "                    left = mid+1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "        return nx(k+1)-nx(k)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "five_powers = [pow(5, i) for i in range(1, 13)]\n",
    "def number_five(n, a):#找n和n前面总共有几个 5 or 25... 的倍数\n",
    "    return n // a\n",
    "def number_ten(n):\n",
    "    global five_powers\n",
    "    cnt = 0\n",
    "    for i in range(len(five_powers)):\n",
    "        cnt += number_five(n, five_powers[i])\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # l\n",
    "        # [15, 20)\n",
    "        #给定n, 后面0的数量为 n sum(number_five(n, power(5, i)))\n",
    "        if k == 1000000000: \n",
    "            return 5\n",
    "        left, right = 0, 1e9 + 10\n",
    "        while left <= right:\n",
    "            #print(left, right)\n",
    "            mid = right + (left - right) // 2\n",
    "            numbers = number_ten(mid)\n",
    "            if numbers < k:\n",
    "                left = mid + 1\n",
    "            elif numbers > k:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                break\n",
    "        #print(number_ten(1e9))\n",
    "        if left <= right:\n",
    "            return 5\n",
    "        else:\n",
    "            return 0\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def preimageSizeFZF(self, k: int) -> int:\r\n",
    "        if k == 0:\r\n",
    "            return 5\r\n",
    "        def get_nk(k):\r\n",
    "            s = k\r\n",
    "            cur = k // 5\r\n",
    "            while cur:\r\n",
    "                s += cur\r\n",
    "                cur = cur // 5\r\n",
    "            return s\r\n",
    "        \r\n",
    "        left, right = k // 2, k+1\r\n",
    "        while left < right:\r\n",
    "            mid = (left + right) // 2\r\n",
    "\r\n",
    "            nk = get_nk(mid)\r\n",
    "\r\n",
    "            if nk == k:\r\n",
    "                return 5\r\n",
    "            elif nk < k:\r\n",
    "                left = mid+1\r\n",
    "            elif nk > k:\r\n",
    "                right = mid\r\n",
    "        return 0\r\n",
    "\r\n",
    "\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "\n",
    "        l, r = 0, 10 ** 18\n",
    "        cnt = 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            cnt = 0\n",
    "            st = 5\n",
    "            while st <= mid:\n",
    "                cnt += mid // st\n",
    "                st *= 5\n",
    "            if cnt >= k:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "            if cnt == k:\n",
    "                return 5\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def f(num):\n",
    "            res = 0\n",
    "            while num:\n",
    "                res += num // 5\n",
    "                num //= 5\n",
    "            return res\n",
    "        l,r = 1, int(1e18)\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            z = f(m)\n",
    "            if z == k:\n",
    "                return 5\n",
    "            if z > k:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return 0\n",
    "    \n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # 5的个数就是0的个数\n",
    "        # 这题最后的结果为5或者0\n",
    "        # 最后可以用二分法\n",
    "        # left为0， right为5 * k\n",
    "\n",
    "        def check(num):\n",
    "            count = 0\n",
    "            while num:\n",
    "                count += num // 5\n",
    "                num //= 5\n",
    "            return count\n",
    "        \n",
    "        low, high = 0, 10 ** 10\n",
    "        while low <= high:\n",
    "            mid = (low + high) >> 1\n",
    "            # 循环不变量：check(high+1) >= k\n",
    "            if check(mid) >= k:\n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        print(low, high)\n",
    "        ans = 0\n",
    "        for num in range(low, low+6):\n",
    "            if check(num) == k:\n",
    "                ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def GetTail0Cnt(n: int) -> int:\n",
    "            res = 0\n",
    "            while n > 0:\n",
    "                n //= 5\n",
    "                res += n\n",
    "            return res\n",
    "        \n",
    "        def nx(k: int) -> int:\n",
    "            return bisect_left(range(5 * k), k, key=GetTail0Cnt)\n",
    "\n",
    "        return nx(k + 1) - nx(k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def check(nums):\n",
    "            cnt = 0\n",
    "            while nums > 0:\n",
    "                cnt += nums // 5\n",
    "                nums //= 5\n",
    "            return cnt\n",
    "        def find(k):\n",
    "            left, right = 0, 5 * k\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if k <= check(mid):\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "        return find(k+1) - find(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def zeta(n: int) -> int:\n",
    "            res = 0\n",
    "            while n:\n",
    "                n //= 5\n",
    "                res += n\n",
    "            return res\n",
    "\n",
    "        def nx(k: int) -> int:\n",
    "            return bisect_left(range(5 * k), k, key=zeta)\n",
    "\n",
    "        return nx(k + 1) - nx(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def zeta(n: int) -> int:\n",
    "            res = 0\n",
    "            while n:\n",
    "                n //= 5\n",
    "                res += n\n",
    "            return res\n",
    "\n",
    "        def nx(k: int) -> int:\n",
    "            return bisect_left(range(5 * k), k, key=zeta)\n",
    "\n",
    "        return nx(k + 1) - nx(k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def get(n):\n",
    "            ans = 0\n",
    "            while n != 0:\n",
    "                n //= 5\n",
    "                ans += n\n",
    "            return ans\n",
    "        \n",
    "        sol = lambda k: bisect.bisect_left(range(k * 5), k, key=get)\n",
    "        return sol(k+1) - sol(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def preimageSizeFZF(self, k: int) -> int:\r\n",
    "        def zeta(n:int):\r\n",
    "            ret=0\r\n",
    "            while n>0:\r\n",
    "                n//=5\r\n",
    "                ret+=n\r\n",
    "            return ret\r\n",
    "        left=0\r\n",
    "        right=5*k+1\r\n",
    "        while left<right:\r\n",
    "            mid=(left+right)//2\r\n",
    "            z=zeta(mid)\r\n",
    "            if z==k:\r\n",
    "                return 5\r\n",
    "            elif z<k:\r\n",
    "                left=mid+1\r\n",
    "            else:\r\n",
    "                right=mid-1\r\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        return self.search(k + 1) - self.search(k)\n",
    "    \n",
    "    def count_zeros(self, num):\n",
    "        res = 0\n",
    "        while num:\n",
    "            res += num // 5\n",
    "            num //= 5\n",
    "        return res\n",
    "    \n",
    "    def search(self, k):\n",
    "        lo, hi = 0, 5 * k\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            zeros = self.count_zeros(mid)\n",
    "            if zeros == k:\n",
    "                hi = mid\n",
    "            elif zeros > k:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "      # for i in range(10, 30):\n",
    "      #   print(i, self.f(i))\n",
    "      if k == 0:\n",
    "        return 5\n",
    "      l, r = 0, 2 ** 63 - 1\n",
    "      while l <= r:\n",
    "        mid = (r - l) // 2 + l\n",
    "        temp = self.f(mid)\n",
    "        if temp == k:\n",
    "          r = mid - 1\n",
    "        if temp > k:\n",
    "          r = mid - 1\n",
    "        if temp < k:\n",
    "          l = mid + 1\n",
    "      left = l\n",
    "      l, r = 0, 2 ** 63 - 1\n",
    "      while l <= r:\n",
    "        mid = (r - l) // 2 + l\n",
    "        temp = self.f(mid)\n",
    "        if temp == k:\n",
    "          l = mid + 1\n",
    "        if temp > k:\n",
    "          r = mid - 1\n",
    "        if temp < k:\n",
    "          l = mid + 1\n",
    "      if self.f(r) == mid:\n",
    "        right = r\n",
    "      else:\n",
    "        right = r - 1\n",
    "      right = r\n",
    "      if right == left:\n",
    "        return 0\n",
    "      return right - left + 1\n",
    "        \n",
    "\n",
    "    def f(self, x):\n",
    "      res = 0\n",
    "      div = 5\n",
    "      while div < x:\n",
    "        res += x // div\n",
    "        div *= 5\n",
    "      return res\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n5 = []\n",
    "n5s = 1\n",
    "for i in range(0,15):\n",
    "    n5s = n5s * 5\n",
    "    n5.append(n5s)\n",
    "\n",
    "def check(val) -> int:\n",
    "    sum = 0\n",
    "    for i in range(0, 15):\n",
    "        sum = sum + val // n5[i]\n",
    "    return sum\n",
    "\n",
    "def find(val) -> int:\n",
    "    l = 0\n",
    "    r = int(6e9)\n",
    "    while l <= r:\n",
    "        mid = (l + r) // 2\n",
    "        if check(mid) < val:\n",
    "            l = mid + 1\n",
    "        else:\n",
    "            r = mid - 1\n",
    "    return l\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        return find(k+1) - find(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, n):\n",
    "        res = 0\n",
    "        while n:\n",
    "            n //= 5\n",
    "            res += n\n",
    "        return res\n",
    "    \n",
    "    def leftBound(self, k):\n",
    "        left, right = 0, 5 * k\n",
    "        while left <= right:\n",
    "            mid = (right - left) // 2 + left\n",
    "            if self.f(mid) >= k:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def rightBound(self, k):\n",
    "        left, right = 0, 10**10\n",
    "        while left <= right:\n",
    "            mid = (right - left) // 2 + left\n",
    "            if self.f(mid) <= k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # return self.rightBound(k) - self.leftBound(k)\n",
    "        return self.leftBound(k + 1) - self.leftBound(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def zete(n):\n",
    "            res = 0\n",
    "            while n!=0 :\n",
    "                n = n // 5\n",
    "                res += n\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        def nk(x):\n",
    "            left = 0\n",
    "            right = 5*x\n",
    "\n",
    "            while left<right:\n",
    "                mid = (left + right) // 2\n",
    "                if zete(mid) <x:\n",
    "                    left = mid+1\n",
    "                else:\n",
    "                    right = mid\n",
    "            \n",
    "            return left \n",
    "        \n",
    "        return nk(k+1) - nk(k)\n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, K: int) -> int:\n",
    "        # 左边界和右边界之差 + 1 就是答案\n",
    "        return int(self.right_bound(K) - self.left_bound(K) + 1)\n",
    "\n",
    "    # 逻辑不变，数据类型全部改成 long\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        divisor = 5\n",
    "        while divisor<=n:\n",
    "            res += n//divisor\n",
    "            divisor*=5\n",
    "        return res\n",
    "        \n",
    "    \"\"\" 搜索 trailingZeroes(n) == K 的左侧边界 \"\"\"\n",
    "    def left_bound(self, target: int) -> int:\n",
    "        lo, hi = 0, 10**10\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if self.trailingZeroes(mid) < target:\n",
    "                lo = mid + 1\n",
    "            elif self.trailingZeroes(mid) > target:\n",
    "                hi = mid \n",
    "            else:\n",
    "                hi = mid\n",
    "                \n",
    "        return lo\n",
    "        \n",
    "    \n",
    "    \"\"\" 搜索 trailingZeroes(n) == K 的右侧边界 \"\"\"\n",
    "    def right_bound(self, target: int) -> int:\n",
    "        lo, hi = 0, 10**10\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if self.trailingZeroes(mid) < target:\n",
    "                lo = mid + 1\n",
    "            elif self.trailingZeroes(mid) > target:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "                \n",
    "        return lo-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "\n",
    "        l, r = 0, 10 ** 9 * 5\n",
    "        cnt = 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            cnt = 0\n",
    "            st = 5\n",
    "            while st <= mid:\n",
    "                cnt += mid // st\n",
    "                st *= 5\n",
    "            if cnt >= k:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "            if cnt == k:\n",
    "                return 5\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        if k == 0: return 5\n",
    "        if k == 1000000000: return 5\n",
    "        def numTrailingZeros(n):\n",
    "            ret = 0\n",
    "            while n > 0:\n",
    "                ret+=n//5\n",
    "                n//=5\n",
    "            return ret\n",
    "        rightB = 10**9+7\n",
    "        def bisectLeft():\n",
    "            left, right = 1, rightB\n",
    "            while left+1 < right:\n",
    "                mid = (left+right)//2\n",
    "                if numTrailingZeros(mid) >=k:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left=mid\n",
    "            if numTrailingZeros(left) == k: return left\n",
    "            if numTrailingZeros(right) == k: return right\n",
    "            return -1\n",
    "        def bisectRight():\n",
    "            left, right = 1, rightB\n",
    "            while left+1 < right:\n",
    "                mid = (left+right)//2\n",
    "                if numTrailingZeros(mid) <= k:\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right=mid\n",
    "            if numTrailingZeros(right) == k: return right\n",
    "            if numTrailingZeros(left) == k: return left\n",
    "            return -1\n",
    "        left, right = bisectLeft(), bisectRight()\n",
    "        # print(left, right)\n",
    "        if left == -1: return 0\n",
    "        return right-left+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # 如果找到f(x) = k 就是5， 否则就是1\n",
    "        l = 0\n",
    "        r = 10**10\n",
    "\n",
    "        def check(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                x //= 5\n",
    "                ans += x\n",
    "            return ans\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) / 2\n",
    "            z = check(mid)\n",
    "            if z == k:\n",
    "                return 5\n",
    "            if z > k:\n",
    "                r = mid - 1\n",
    "            elif z < k:\n",
    "                l = mid + 1\n",
    "            \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def ZeroCnt(n: int) -> int:\n",
    "            res = 0\n",
    "            while n > 0:\n",
    "                n //= 5\n",
    "                res += n\n",
    "            return res\n",
    "        \n",
    "        def GetRes(x: int) -> int:\n",
    "            return bisect_left(range(5 * x), x, key=ZeroCnt)\n",
    "\n",
    "        return GetRes(k + 1) - GetRes(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # 5的个数就是0的个数\n",
    "        # 这题最后的结果为5或者0\n",
    "        # 最后可以用二分法\n",
    "        # left为0， right为5 * k\n",
    "\n",
    "        def check(num):\n",
    "            count = 0\n",
    "            while num:\n",
    "                count += num // 5\n",
    "                num //= 5\n",
    "            return count\n",
    "        \n",
    "        low, high = 0, 10 ** 10\n",
    "        while low <= high:\n",
    "            mid = (low + high) >> 1\n",
    "            # 循环不变量：check(high+1) >= k\n",
    "            if check(mid) >= k:\n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for num in range(high+1, high+6):\n",
    "            if check(num) == k:\n",
    "                ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def zeta(n: int) -> int:\n",
    "            res = 0\n",
    "            while n:\n",
    "                n //= 5\n",
    "                res += n\n",
    "            return res\n",
    "\n",
    "        def nx(k: int) -> int:\n",
    "            return bisect_left(range(5 * k), k, key=zeta)\n",
    "\n",
    "        return nx(k + 1) - nx(k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "\n",
    "        # 计算num的阶乘0个数\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            while num > 0:\n",
    "                cnt += num//5\n",
    "                num //= 5\n",
    "            return cnt\n",
    "\n",
    "        # 二分查找确定阶乘0的个数为k的下界\n",
    "        low = 0\n",
    "        high = 10**10\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid) >= k:\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "\n",
    "        # 找出符合条件的数字个数（每隔6个数阶乘0必然会有增加）\n",
    "        if check(low+1) == k:\n",
    "            return 5\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        return int(self.right_bound(k) - self.left_bound(k) + 1)\n",
    "    \n",
    "\n",
    "\n",
    "    def trailingzero(self, n):\n",
    "        res = 0\n",
    "        divider = 5\n",
    "        while n >= divider:\n",
    "            res += n // divider\n",
    "            n = n //divider\n",
    "        return res\n",
    "    \n",
    "\n",
    "\n",
    "    def left_bound(self, target):\n",
    "        left, right = 0, 2**63 - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.trailingzero(mid) >= target:\n",
    "                right = mid - 1\n",
    "            elif self.trailingzero(mid) < target:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left\n",
    "    \n",
    "\n",
    "    def right_bound(self, target):\n",
    "        left, right = 0, 2**63 - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if self.trailingzero(mid) <= target:\n",
    "                left = mid + 1\n",
    "            elif self.trailingzero(mid) > target:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left - 1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "\n",
    "        # 计算num的阶乘0个数\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            while num > 0:\n",
    "                cnt += num//5\n",
    "                num //= 5\n",
    "            return cnt\n",
    "\n",
    "        # 二分查找确定阶乘0的个数为k的下界\n",
    "        low = 0\n",
    "        high = 10**10\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid) >= k:\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "\n",
    "        # 最后答案只能是0或5\n",
    "        if check(low+1) == k:\n",
    "            return 5\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        return self.findRight(k) - self.findLeft(k) + 1\n",
    "\n",
    "    def findLeft(self, k):\n",
    "        left = 0\n",
    "        right = sys.maxsize\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.trailingZeroes(mid) >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def findRight(self, k):\n",
    "        left = 0\n",
    "        right = sys.maxsize\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.trailingZeroes(mid) > k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right - 1\n",
    "\n",
    "\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "        div = 5\n",
    "        while div <= n:\n",
    "            res += n // div\n",
    "            div *= 5\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def get_tail_zreos(n:int):\n",
    "            cnt = 0\n",
    "            divisor = 5\n",
    "            while divisor <= n:\n",
    "                cnt += (n // divisor)\n",
    "                divisor *= 5\n",
    "            return cnt\n",
    "        \n",
    "        # 二分查找阶乘之后尾号为0的个数刚好是k的最小数\n",
    "        left = 0\n",
    "        right = k * 5 # 关键1\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            cnt = get_tail_zreos(mid)\n",
    "            if cnt < k:\n",
    "                left = mid + 1\n",
    "            elif cnt > k:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                # 关键2:最后结果只会是0或者5\n",
    "                return 5\n",
    "\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        def getK0(x: int) -> int:\n",
    "            factor = 5\n",
    "            ans = 0\n",
    "            while factor <= x:\n",
    "                ans += x//factor\n",
    "                factor *= 5\n",
    "            return ans\n",
    "\n",
    "        l, r = 0, int(1e10)\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if getK0(mid) >= k:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        ans = 0\n",
    "        while getK0(l) == k:\n",
    "            ans += 1\n",
    "            l += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        #2，5，n*10的数量，注意25，125,625中包含多个5.\n",
    "        #n！的末尾0的数量=1,2,3....n中因数5的个数\n",
    "        #假设f(n)=(5**n)!的末尾0的个数，则分解k=a1*f(1)+a2*f(2)+...+ax*f(x)\n",
    "        #要求0<=ai<=4\n",
    "        f = {0:0}\n",
    "        next_zero_num = 0\n",
    "        n = 0\n",
    "        while next_zero_num <= k:\n",
    "            n += 1\n",
    "            next_zero_num = 5 ** (n-1) + next_zero_num\n",
    "            f[n] = next_zero_num\n",
    "        for i in range(n-1, 0, -1):\n",
    "            print(k, f[i])\n",
    "            if k // f[i] > 4:\n",
    "                return 0\n",
    "            k = k % f[i]\n",
    "        return 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 函数仅用来验证k!末尾含0的个数\n",
    "    def numZero(self, k: int) -> int:\n",
    "        if k==0:\n",
    "            return 0\n",
    "        t = 0 \n",
    "        tk = k\n",
    "        while tk%5 == 0:\n",
    "            t += 1\n",
    "            tk /= 5\n",
    "        return self.numZero(k-1)+t\n",
    "\n",
    "    # 规模在10e9，因此本质是个数学问题\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # 5e13恰大于10e9\n",
    "        pp = []\n",
    "        t = 0\n",
    "        pp.append(1)\n",
    "        ## 统计5^i末尾0的个数\n",
    "        for i in range(1,14):\n",
    "            pp.append(pp[i-1]*5+1)\n",
    "            if pp[i] > k and pp[i-1] <= k:\n",
    "                t = i\n",
    "                break\n",
    "        #return self.numZero(505)\n",
    "\n",
    "        # 对于k, 判断其离a*5^i末尾含0数的距离距离，离得近就不存在\n",
    "        for i in range(t,0,-1):\n",
    "            if pp[i] - k%pp[i] <= i:\n",
    "                return 0\n",
    "            k = k % pp[i]\n",
    "        return 5\n",
    "        # 结果不是0就是5\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        l = 0\n",
    "        r = pow(2,64)\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + (r-l) // 2\n",
    "            cur = self.helper(mid)\n",
    "\n",
    "            if cur == k:\n",
    "                r = mid\n",
    "            elif cur > k:\n",
    "                r = mid\n",
    "            elif cur < k:\n",
    "                l = mid + 1\n",
    "        left_bound = l\n",
    "\n",
    "        l = 0\n",
    "        r = pow(2,64)\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + (r-l) // 2\n",
    "            cur = self.helper(mid)\n",
    "\n",
    "            if cur == k:\n",
    "                l = mid + 1\n",
    "            elif cur < k:\n",
    "                l = mid + 1\n",
    "            elif cur > k:\n",
    "                r = mid\n",
    "        right_bound = l - 1\n",
    "\n",
    "        return right_bound - left_bound + 1\n",
    "\n",
    "    def helper(self, n):\n",
    "        res = 0\n",
    "        divisor = 5\n",
    "\n",
    "        while n >= divisor:\n",
    "            res += n // divisor\n",
    "            divisor *= 5\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "\n",
    "        return self.foundright(k) - self.foundleft(k) + 1\n",
    "    \n",
    "    def foundleft(self, k):\n",
    "        left, right = 0, sys.maxsize\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.f(mid) >= k:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "    \n",
    "    def foundright(self, k):\n",
    "        left, right = 0, sys.maxsize\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.f(mid) > k:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right\n",
    "\n",
    "\n",
    "\n",
    "    def f(self, x):\n",
    "        res = 0\n",
    "        c = 1\n",
    "        d = 5 ** c\n",
    "        while d <= x:\n",
    "            res += x // d\n",
    "            c += 1\n",
    "            d = 5 ** c\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, K: int) -> int:\n",
    "        # 左边界和右边界之差 + 1 就是答案\n",
    "        return int(self.right_bound(K) - self.left_bound(K) + 1)\n",
    "    \n",
    "    # 搜索 trailingZeroes(n) == K 的左侧边界\n",
    "    def left_bound(self, target: int) -> int:\n",
    "        lo, hi = 0, 1 << 63 - 1\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if self.trailingZeroes(mid) < target:\n",
    "                lo = mid + 1\n",
    "            elif self.trailingZeroes(mid) > target:\n",
    "                hi = mid\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo\n",
    "    \n",
    "    # 搜索 trailingZeroes(n) == K 的右侧边界\n",
    "    def right_bound(self, target: int) -> int:\n",
    "        lo, hi = 0, 1 << 63 - 1\n",
    "        while lo < hi:\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            if self.trailingZeroes(mid) < target:\n",
    "                lo = mid + 1\n",
    "            elif self.trailingZeroes(mid) > target:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo - 1\n",
    "\n",
    "    def trailingZeroes(self, n: int) -> int:\n",
    "        res = 0\n",
    "\n",
    "        divisor = 5\n",
    "        while divisor <= n:\n",
    "            res += n // divisor\n",
    "            divisor *= 5\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(index):\n",
    "    res = 0\n",
    "    while index and index % 5 == 0:\n",
    "        index //= 5\n",
    "        res += index\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def preimageSizeFZF(self, k: int) -> int:\n",
    "        # l = 0; r = 5*k\n",
    "        # while l < r:\n",
    "        #     m = (l+r) // 2\n",
    "        #     if f(m) < k: l = m + 1\n",
    "        #     else: r = m\n",
    "        # print(l, r)\n",
    "        # return 5 if r % 5 == 0 else 0\n",
    "        i = 1\n",
    "        while i < k: i = i*5+1\n",
    "        while i > 1:\n",
    "            if i-1 == k: return 0\n",
    "            i = (i-1) // 5\n",
    "            k %= i\n",
    "        return 5\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
